<head>
    <meta charset="UTF-8">
<title>算法训练 Eurodiffusion</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">【问题描述】</span></font></p>
<p class="western" style="margin-bottom: 0in">2002<font face="微软雅黑"><span lang="zh-CN">年</span></font>1<font face="微软雅黑"><span lang="zh-CN">月</span></font>1<font face="微软雅黑"><span lang="zh-CN">日，</span></font>12<font face="微软雅黑"><span lang="zh-CN"><font face="微软雅黑">个欧洲国家放弃了它们原来的货币，开始使用欧元。从此，在整个欧元区，再也没有了法郎、马克、里拉、基尔德、克朗</font><font face="Times New Roman, serif">&hellip;&hellip;</font><font face="微软雅黑">，只有欧元。这些国家使用的纸币相同，但是硬币也相同？不完全是这样。每个国家都有一定的自由来制造自己的欧元硬币：</font></span></font></p>
<p class="western" style="margin-bottom: 0in"><span lang="zh-CN">&ldquo;<font face="微软雅黑">每个欧元硬币的一面都有同样的欧洲地形，在另一面，成员国可以用自己的图形装饰硬币。无论哪种图形的硬币，都可以在</font></span>12<span lang="zh-CN"><font face="微软雅黑" style="font-family: 微软雅黑; ">个成员国的任何地方使用。比如，一个法国公民可以使用含有西班牙国王印记的欧元硬币，在柏林买到一个热狗。</font><font face="Times New Roman, serif">&rdquo;</font><font face="微软雅黑" style="font-family: 微软雅黑; ">（来源于</font></span>http://europa.eu.int/euro/html/entry.html<font face="微软雅黑"><span lang="zh-CN">）</span></font></p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">在</span></font>2002<font face="微软雅黑"><span lang="zh-CN">年</span></font>1<font face="微软雅黑"><span lang="zh-CN">月</span></font>1<font face="微软雅黑"><span lang="zh-CN">日，巴黎唯一的欧元硬币是法国硬币。不久，第一种非法国硬币出现在巴黎。最终，人们可能会认为所有类型的硬币平均分布在</span></font>12<font face="微软雅黑"><span lang="zh-CN">个成员国（其实并不是这样，因为所有国家一直都在发行自己的硬币，所以即使在稳定的情况下，在柏林，德国硬币应该都是最多的）。所以，多久以后芬兰或爱尔兰的硬币才会第一次在意大利南部流通？每种硬币要多久以后才能出现在所有的地方？</span></font></p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">因此，你需要写一个程序来模拟欧元硬币在整个欧洲的传播过程。这里使用一种高度简化的模型，考虑单一的欧元面额。给出一个矩形网格，欧洲城市都在格点上，每个城市最多可以有</span></font>4<font face="微软雅黑"><span lang="zh-CN">个邻接的城市（东西南北各一个）。每个城市都属于且仅属于一个国家，而且一个国家所有城市在平面上刚好组成一个矩形。下图是一个含有</span></font>3<font face="微软雅黑"><span lang="zh-CN">个国家、</span></font>28<font face="微软雅黑"><span lang="zh-CN">个城市的地图。</span></font></p>
<p class="western" style="margin-bottom: 0in">&nbsp;<img src="http://lx.lanqiao.cn/RequireFile.do?fid=yNEHABeq" width="246" height="196" alt="" /></p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN"><font face="微软雅黑">在地图上，国家之间是连通的，但国家之间可能含有洞，这表示海洋或像瑞士、丹麦这样的非欧元区国家。一开始，每个城市都只有一百万个本国的硬币，然后每一天，每个城市都按照它在这一天开始时的余额，将一定量的硬币送给它的所有邻接城市。这</font><font face="Times New Roman, serif">&rdquo;</font><font face="微软雅黑">一定量的硬币</font><font face="Times New Roman, serif">&ldquo;</font><font face="微软雅黑">指的是对于这个城市目前所拥有的每种图形的硬币，每满</font></span></font>1000<font face="微软雅黑"><span lang="zh-CN">个就要拿出来一个。</span></font></p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">当某个<font face="微软雅黑">城市中，每种图形的硬币都至少出现了一个，</font>就称这个<font face="微软雅黑">城市</font><font face="Times New Roman, serif">&ldquo;</font><font face="微软雅黑">已经完成</font><font face="Times New Roman, serif">&rdquo;</font><font face="微软雅黑">。当一个国家的所有城市都已经完成的时候，就称这个国家已经完成。你的程序需要得出每个国家的完成时间。</font></span></font></p>
<p class="western" style="margin-bottom: 0in">&nbsp;</p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">【输入格式】</span></font></p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">输入包含多组数据。每组数据的第一行是一个数</span></font><i>c</i><font face="微软雅黑"><span lang="zh-CN">，表示国家的个数，接下来</span></font>c<font face="微软雅黑"><span lang="zh-CN">行，每行描述一个国家。对于国家的描述按照以下格式：</span></font><i>name xl yl xh yh</i><font face="微软雅黑"><span lang="zh-CN">，其中</span></font><i>name</i><font face="微软雅黑"><span lang="zh-CN">是一个最多</span></font>25<font face="微软雅黑"><span lang="zh-CN">个字符的字符串，表示国家名称，</span></font><i>(xl, yl)</i><font face="微软雅黑"><span lang="zh-CN">表示这个国家左下角（西南角）的城市坐标，</span></font><i>(xh, yh)</i><font face="微软雅黑"><span lang="zh-CN">表示这个国家右上角（东北角）的城市坐标。</span></font></p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">最后一组数据之后是一个</span></font>0<font face="微软雅黑"><span lang="zh-CN">。</span></font></p>
<p class="western" style="margin-bottom: 0in">&nbsp;</p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">【输出格式】</span></font></p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">对于每组数据，先输出一行表示数据编号，接下来对每个国家输出一行，包括这个国家的名称以及它的完成时间（单位：天）。国家之间按照完成时间递增排序，如果两个国家的完成时间相同，按照国家名称的字典序递增排序。</span></font></p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">按照样例输出的格式输出（国家名称之前空</span></font>3<font face="微软雅黑"><span lang="zh-CN">格，国家名称和完成时间之间空</span></font>3<font face="微软雅黑"><span lang="zh-CN">格，样例输出在排版的时候可能出了一点问题）。</span></font></p>
<p class="western" style="margin-bottom: 0in">&nbsp;</p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">【样例输入】</span></font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">3</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">France 1 4 4 6</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">Spain 3 1 6 3</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">Portugal 1 1 2 2</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">1</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">Luxembourg 1 1 1 1</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">2</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">Netherlands 1 3 2 4</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">Belgium 1 1 2 2</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">0</font></p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN">【样例输出】</span></font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">Case Number 1</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">&nbsp; &nbsp;Spain &nbsp; 382</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">&nbsp; &nbsp;Portugal &nbsp; 416</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">&nbsp; &nbsp;France &nbsp; 1325</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">Case Number 2</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">&nbsp; &nbsp;Luxembourg &nbsp; 0</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">Case Number 3</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">&nbsp; &nbsp;Belgium &nbsp; 2</font></p>
<p class="western" style="margin-bottom: 0in"><font face="Droid Sans Mono, sans-serif">&nbsp; &nbsp;Netherlands &nbsp; 2</font></p>
<p class="western" style="margin-bottom: 0in"><font face="微软雅黑"><span lang="zh-CN"><font face="微软雅黑">【</font>数据规模和约定<font face="微软雅黑">】</font></span></font></p>
<p class="western" style="margin-bottom: 0in">1&lt;=<i>c</i>&lt;=20<font face="微软雅黑"><span lang="zh-CN">，</span></font>1&lt;=<i>xl</i>&lt;=<i>xh</i>&lt;=10<font face="微软雅黑"><span lang="zh-CN">，</span></font>1&lt;=<i>yl</i>&lt;=<i>yh</i>&lt;=10<font face="微软雅黑"><span lang="zh-CN">。</span></font></p>